package leetcode;

/*
868. 二进制间距
给定一个正整数 N，找到并返回 N 的二进制表示中两个相邻 1 之间的最长距离。
如果没有两个相邻的 1，返回 0 。
示例 1：
输入：22
输出：2
解释：
22 的二进制是 0b10110 。
在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。
第一对相邻的 1 中，两个 1 之间的距离为 2 。
第二对相邻的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。
示例 2：
输入：5
输出：2
解释：
5 的二进制是 0b101 。
示例 3：
输入：6
输出：1
解释：
6 的二进制是 0b110 。
示例 4：
输入：8
输出：0
解释：
8 的二进制是 0b1000 。
在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。
提示：
1 <= N <= 10^9
*/

public class problems_868 {
    public static void main(String[] args) {
        System.out.println(new Solution().binaryGap(6));
    }

    static class Solution {
        public int binaryGap(int n) {
            if(n == 0) return 0;
            // 转为二进制
            StringBuffer strB = new StringBuffer(32);
            while (n > 0) {
                strB.append(n%2);
                n = n >> 1;
            }
            // 前去零
            String str = strB.toString().replaceAll("^(0+)", "");
            // 只有一个1
            if(str.indexOf("1") == str.lastIndexOf("1")) return 0;
            //
            int max = 1;
            for (String split : str.split("1")){
                max = Math.max(max, split.length() + 1);
            }
            return max;
        }
    }

//    static class Solution {
//        public int binaryGap(int n) {
//            int max = 0;
//            int num = 0;
//            while (n > 0) {
//                System.out.println(n%2 + "__n:"  + n);
//                num = n % 2 == 1 ? num + 1 : 0;
//                max = Math.max(max, num);
//                n = n >> 1;
//            }
//            return max;
//        }
//    }
}